HW#3 --- last modified February 17 2019 19:41:06..

Solution set.

Due date: Apr 15

Files to be submitted:
  Hw1.zip

Purpose: Get familiar with various data structures used in geometric modeling.

Related Course Outcomes:

The main course outcomes covered by this assignment are:

(6) Know the advantages and disadvantages of different mesh representations
(7) Understand and use scene graphs
(8) Implement and use BSP trees (actually octrees)

Specification:

For this assignment I want you to write programs which can convert between various representation schemes. To start with, data for a scene you are going to render is assumed to be in a text file. The first line in this file specifies the size of a box in which the whole scene lives. For instance, if this first line was:

2.6

Then the `x`, `y`, `z`, boundaries of the world box would be `\pm 2.6`.

After the first line in the scene text file, the format we will use is to have list a sequence of objects. An object begins with the string 'obj' on it and ends with the line 'endobj'. For example,

obj
... data for the object ...
endobj

Objects are described in postfix order. A line in an object can either describe a planar half-space or can be a regularized set operation. A line for a half-space looks like:
`\pm:A:B:C:D`

A plus indicates the half-space `H_(+)`, minus indicates the half-space `H_(-)`. `A`, `B`, `C`, and `D` are floating point coefficients for the plane `Ax + By + Cz + D = 0`. A line with a single ASCII letter amongst U for union, I for intersection can be used to indicate a regular set operation. Note these are the only regular operation you need to implement.

The filename of the particular file that your program should operate on should be a hard-coded constant featured somewhere prominently in your code. A readme.txt file should be included as in HW2 which says where the filename is set as well as anything else I need to do to test your code. You should include with your project at least three test files one of which needs to have a fair number of objects in it.

Given such an input file I want your program to do two main things. First, take the above representations of objects and convert each to Winged Edge Representation and pretty print the result to the console. Next, I want you to compute an octree of the scene based on the objects in the scene and pretty print that to the console. You can cut off the octree recursion at some dept even if not all octants are completely covered or not.

As a suggestion, I would try to use a recursive algorithm that traverses the input in postfix order. Maintain the property that the arguments to whatever operation you need to do are always unions of intersections of half spaces. Finally, compute the winged edge representation of each final intersection you get. The union of these can be the winged-edge representation of the whole figure.

For 3 bonus points, you can also draw the scene from a decent angle.

Point Breakdown